package heap;

import java.util.Arrays;
import java.util.Random;

/**
 * 
 * @Title: CandyHeapSort.java 
 * @Package heap 
 * @Description: 堆排序
 * @author CandyWall   
 * @date 2021年1月9日 上午9:25:44 
 * @version V1.0
 */
public class CandyHeapSort {
    private CandyHeapSort() {}

    /**
     * 将数组中的元素依次放入到一个空堆中，构建一个最大堆
     * 构建完成后，每次取出堆顶元素，每取一次就调整一次最大堆
     * @param data
     */
    public static <E extends Comparable<E>> void sort1(E[] data) {
        CandyMaxHeap<E> maxHeap = new CandyMaxHeap();
        for(E e : data) {
            maxHeap.add(e);
        }
        for(int i = data.length - 1;i >= 0; i--) {
            data[i] = maxHeap.extractMax();
        }
    }
    
    /**
     * 直接根据该数组构建一个最大堆
     * 构建完成后，每次取出堆顶元素，每取一次就调整一次最大堆
     * @param data
     */
    public static <E extends Comparable<E>> void sort2(E[] data) {
        if(data.length - 1 <= 1) {
            return;
        }
        for(int i = (data.length - 2) / 2; i >= 0; i--) {
            shiftDown(data, i, data.length);
        }
        
        for(int i = data.length - 1; i >= 0; i--) {
            swap(data, 0, i);
            shiftDown(data, 0, i);
        }
    }
    
    // 对 data[0,n) 所形成的最大堆中，索引为i的元素执行shiftDown操作
    private static <E extends Comparable<E>> void shiftDown(E[] data, int i, int n) {
        while(i * 2 + 1 < n) {
            int j = i * 2 + 1;
            if(j + 1 < n && data[j + 1].compareTo(data[j]) > 0) {
                j++;
            }
            if(data[i].compareTo(data[j]) >= 0) {
                break;
            }
            swap(data, i, j);
            i = j;
        }
    }
    
    private static <E> void swap(E[] data, int i, int j) {
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
    
    public static void main(String[] args) {
        int n = 1000;
        Random random = new Random();
        Integer[] arr1 = new Integer[n];
        for(int i = 0; i < n; i++) {
            arr1[i] = random.nextInt(n);
        }
        // System.arraycopy(arr1, 0, arr2, 0, n);
        Integer[] arr2 = Arrays.copyOf(arr1, n);
        sort1(arr1);
        System.out.println(Arrays.toString(arr1));
        sort2(arr2);
        System.out.println(Arrays.toString(arr2));
    }
}
